package com.gxc.linkedList;

public class Intersect {

    public static void main(String[] args) {
        //非环链表
        Node head = Loopback.createNode();
        boolean isRing = isRing(head);
        System.out.println(isRing(head));
        System.out.println(getLastNode(head).value);
        //环链表
        head = Loopback.createRingNode();
        System.out.println(isRing(head));
        System.out.println(entryRingNode(head).value);

        Node head1 = Loopback.createNode();
        Node head2 = Loopback.createNode();
        boolean isIntersect = isIntersect(head, head);
        System.out.println(isIntersect);

        //非环相交
        head = Loopback.createNode();
        Node intersectionPoint = intersectionPoint(head, head);
        System.out.println(intersectionPoint.value);

        //环入环点相同
        head = Loopback.createRingNode();
        intersectionPoint = intersectionPoint(head, head);
        System.out.println(intersectionPoint.value);

        //环入环点不同
        head = Loopback.createRingNode();
        intersectionPoint = intersectionPoint(head, head);
        System.out.println(intersectionPoint.value);
    }

    /**
     * 链表相交点
     * @param head1
     * @param head2
     * @return
     */
    private static Node intersectionPoint(Node head1, Node head2) {
        boolean head1IsRing = isRing(head1);
        boolean head2IsRing = isRing(head2);

        //链表都为非环，如果相交则最后node肯定相同
        if (!head1IsRing && !head2IsRing) {
            int gap = 0;
            Node lastNode1 = head1;
            while (lastNode1.next!=null) {
                gap++;
                lastNode1 = lastNode1.next;
            }

            Node lastNode2 = head2;
            while (lastNode2.next!=null) {
                gap--;
                lastNode2 = lastNode2.next;
            }
            if (lastNode1 == lastNode2) {
                Node longerNode = gap>=0?head1:head2;
                Node shortNode = gap>=0?head2:head1;
                gap = Math.abs(gap);
                while (gap>0) {
                    longerNode = longerNode.next;
                    gap--;
                }
                while (longerNode!=shortNode) {
                    longerNode = longerNode.next;
                    shortNode = shortNode.next;
                }
                return longerNode;
            }
            return null;
        } else if (head1IsRing && head2IsRing) {
            //链表都为环，可能相交
            Node entryRingNode1 = entryRingNode(head1);
            Node entryRingNode2 = entryRingNode(head2);
            //入环点相同
            if (entryRingNode1 == entryRingNode2) {
                int gap = 0;
                Node lastNode1 = head1;
                while (lastNode1!=entryRingNode1) {
                    gap++;
                    lastNode1 = lastNode1.next;
                }
                Node lastNode2 = head2;
                while (lastNode2!=entryRingNode2) {
                    gap--;
                    lastNode2 = lastNode2.next;
                }
                Node longerNode = gap>=0?head1:head2;
                Node shortNode = gap>0?head2:head1;
                while (gap>0) {
                    longerNode = longerNode.next;
                    gap--;
                }
                while (longerNode!=shortNode) {
                    longerNode = longerNode.next;
                    shortNode = shortNode.next;
                }
                return longerNode;
            }
            //入环点不相同
            Node next = entryRingNode1.next;
            while (next!=entryRingNode1) {
                if (next == entryRingNode2) return entryRingNode2;
                next = next.next;
            }
            return null;
        } else {
            //链表一个为非环，一个为环，不可能相交
            return null;
        }
    }

    /**
     * 判断链表是否相交
     * @param head1
     * @param head2
     * @return
     */
    private static boolean isIntersect(Node head1, Node head2) {
        boolean head1IsRing = isRing(head1);
        boolean head2IsRing = isRing(head2);

        //链表都为非环，如果相交则最后node肯定相同,让长度更长的链表先走两个链表的长度差值，然后开始同时走，相遇时则为第一个相交点
        if (!head1IsRing && !head2IsRing) {
            Node lastNode1 = getLastNode(head1);
            Node lastNode2 = getLastNode(head2);
            if (lastNode1 == lastNode2) {
                return true;
            }
            return false;
        } else if (head1IsRing && head2IsRing) {
            //链表都为环，可能相交
            Node entryRingNode1 = entryRingNode(head1);
            Node entryRingNode2 = entryRingNode(head2);
            //入环点相同
            if (entryRingNode1 == entryRingNode2) return true;

            //入环点不相同
            Node next = entryRingNode1.next;
            while (next!=entryRingNode1) {
                if (next == entryRingNode2) return true;
                next = next.next;
            }
            return false;
        } else {
            //链表一个为非环，一个为环，不可能相交
            return false;
        }
    }

    /**
     * 非环聊表最后一个node
     * @param head
     * @return
     */
    private static Node getLastNode(Node head) {
        Node node = head;
        while (node.next!=null) {
            node = node.next;
        }
        return node;
    }

    /**
     * 判断链表是否有环
     * @param head
     */
    private static boolean isRing(Node head) {
        if (head == null) return false;
        Node fast = head;
        Node slow = head;

        while (fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == null) return false;
            //快慢指针相撞，说明有环
            if (fast == slow) return true;
        }
        return false;
    }

    /**
     * 入环的第一个node
     * @param head
     * @return
     */
    private static Node entryRingNode(Node head) {
        if (head == null) return null;
        Node fast = head;
        Node slow = head;

        while (fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast!=slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

}
